package com.leetcode;

/**
 * 某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。
 * <p>
 * 要求实现时间复杂度为 O(n) 的算法。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：sales = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。
 * 示例 2：
 * <p>
 * 输入：sales = [5,4,-1,7,8]
 * 输出：23
 * 解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。
 */
public class LCR161 {
    public int maxSales(int[] sales) {
        // 某一天, 如果前面连续的利润大于0, 可以连续
        int result = Integer.MIN_VALUE;
        int[] dp = new int[sales.length];
        for (int i = 0; i < sales.length; i++) {
            if (i == 0) {
                dp[i] = sales[i];
            } else {
                dp[i] = Math.max(sales[i], dp[i - 1] + sales[i]);
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}
